Incremental Bridge-Connectivity
Operations
$ n頂点の無向グラフを扱う
空間計算量$ \Theta(n)
$ \mathtt{new}(n)
$ n頂点の辺を持たないグラフを作成する.
時間計算量$ \Theta(n \log n) \ \rm amortized
$ \mathtt{insert\_edge}(u, v)
無向辺$ (u, v)を追加する.
時間計算量$ \Theta(1) \ \rm amortized
$ \mathtt{bridge\_connected}(u, v)
$ uと$ vが二辺連結か判定する.
時間計算量$ \Theta(1) \ \rm amortized
Summary
また, 二辺連結成分を圧縮して得られる森を, 各頂点が親を保持する形で管理する.
$ \mathtt{insert\_edge}(u, v)
$ uと$ vが非連結の場合
$ uの属する木が$ vのそれより小さいとする.
適宜辺を反転して$ uを根にし, $ uの親を$ vにすることで木を連結する.
https://gyazo.com/85427022234ddb8defcdd130bd389179
$ uと$ vが連結の場合
$ uvパス上の頂点を全て同じ二辺連結成分としてまとめる.
$ uと$ vから交互に親を辿ることにより, $ uvパス長のオーダーでパス上の頂点を列挙する.
https://gyazo.com/c2a28c741b2c5647716f9e5da2441586
References
Notes
内部で二辺連結成分のUnion Findを管理しているため, 連結性判定の他にも代表元の取得などが可能. ある辺が橋であるかどうかの判定もできる
$ uと$ vが非連結の場合は, 辺$ (u, v)に橋フラグを立てる
$ uと$ vが連結の場合, $ uvパス上の辺の橋フラグを取り除く
よりオーダーが高速なアルゴリズムも同論文で示されている.
Implementations